1. Technical Field
The present invention relates to global routing in printed circuit board (PCB) routing and in physical design of integrated VLSI circuits.
2. Description of Related Art
Global routing is a critical step in the physical design of integrated circuits and is a NP-hard (Non-deterministic Polynomial-time hard) problem as described in T. Langauer, Combinational algorithms for integrated circuit and layout, John Wiley & Sons, New York, 1990. Global routing lies between placement and detailed-routing steps in the physical design of VLSI (Very Large Scale Integration) chips. In global routing, nets of wires are mapped to a coarse grid of global routing cells (or gcells). Each gcell has a fixed horizontal and vertical capacity. The objective of global routing is to assign the nets while satisfying capacity constraints (horizontal and vertical) of the gcells as described in H. Y. Chen and Y. W. Chang, Electronic Design Automation: Synthesis, Verification, and Testing, Elsevier Morgan Kaufmann, pp. 687-749 (2009). Each net is routed by generating a spanning tree for it that covers all of its pins. A solution of the global routing problem that does not violate the capacity constraints of the gcells is a valid solution. Routability-driven (RD) placement is a recent development that uses global routing to guide the placement process. The RD placement is described in X. He. T. Huang, L. Xiao, H. Tian, and E. F. Y. Yong, Ripple: A robust and effective routabiltiy-driven placer, IEEE Trans. Computer Aided Design of Integrated Circuits and Systems, 32, (10), pp. 1546-1556, (2013) and M. Pan, and C. Chu, FastRoute: A Step to Integrate Global Routing into Placement, IEEE/ACM International Conference on Computer-Aided design, San Jose, Calif., November 2006, pp. 464-471. The RD placement process needs to execute global routing several times. Therefore, global routers should have good solution quality and runtime.
Among the methods of routing, maze routing is the only method that guarantees to find a path between any two pins if there exists one. Therefore, many global routers use maze routing exclusively, or use other methods for initial routing and use maze routing for difficult-to-route nets as described in K. Suzuki, Y. Matsunaga, M. Tachibana, and T. Ohtsuki, A hardware maze router with application to interactive rip-up and reroute, IEEE Trans. Computer-Aided Design, CAD, 5(4), 155-157 and M. Pan, U. Xu, X. Zhang, and C. Chu, FastRoute: An efficient and high-quality global router, VLSI design, Hindawi Publishing Corporation, (2012). However, maze routing is slow and memory intensive. Maze routing is generally used with a rip-up and re-route (R&R) process to produce valid solutions. The main task of the R&R process is to selectively rip-up and re-route a small fraction of nets in order to eliminate congestion. Maze routing with framing (MRF) is a modification of maze routing in which a net determines its spanning tree within a bounding box of the grid. The MRF method is described in S. Sait and H. Youssef, VLSI Physical Design and Automation: Theory and Practice, World Scientific Publishers, 243-244, 1999. The MRF method is very fast as compared to traditional maze routing and the size of the bounding box can be increased or decreased. Lee algorithm is a popular method of maze routing and has a breath-first behavior. Recent research showed that Lee algorithm is highly suitable for implementation using parallel computing platforms such as graphics processor units (GPUs) because of its simple data-structure and breath-first behavior which can be easily implemented on parallel platforms. Lee algorithm is described in in S. Sait and H. Youssef, VLSI Physical Design and Automation: Theory and Practice, World Scientific Publishers, 239-241, 1999.
GT based algorithms have been used in routing of communication networks, multi-agent optimization problem and wireless networking as described in F. N. Pavlidou and G. Koltisdas, Game theory for routing modeling in communication networks, A survey, Journal of Communications and Networks, 10 (3) (2008), 268-286, A. Salhi and O. Toreyen, Computational Intelligence in Optimization, Springer-Verlag Berlin, Heidelberg, (2010), pp. 211-232, and L. A. DaSilva, H. Bogucka and A. MacKenzie, Game theory in wireless networks, IEEE Communications Magazine, 49 (8), (2011), 110-111.
The good performance of GT in solving congestion problems in computers and communication networks motivates its use in solving the global routing problem of VLSI physical design.
The foregoing “Background” description is for the purpose of generally presenting the context of the disclosure. Work of the inventor, to the extent it is described in this background section, as well as aspects of the description which may not otherwise qualify as prior art at the time of filing, are neither expressly or impliedly admitted as prior art against the present invention. The foregoing paragraphs have been provided by way of general introduction, and are not intended to limit the scope of the following claims. The described embodiments, together with further advantages, will be best understood by reference to the following detailed description taken in conjunction with the accompanying drawings.